import java.util.*;

/**
 * 341. 扁平化嵌套列表迭代器
 * https://leetcode-cn.com/problems/flatten-nested-list-iterator/
 */
public class Solutions_341 {
    public static void main(String[] args) {
        NestedInteger nest = new NestedInteger();

        NestedInteger nest1 = new NestedInteger();
        nest1.add(new NestedInteger(1));
        nest1.add(new NestedInteger(1));
        nest.add(nest1);

        NestedInteger nest2 = new NestedInteger(2);
        nest.add(nest2);

        NestedInteger nest3 = new NestedInteger();
        nest3.add(new NestedInteger(1));
        nest3.add(new NestedInteger(1));
        nest.add(nest3);

        // {{1, 1}, 2, {1, 1}}
        // output: {1, 1, 2, 1, 1}

        NestedIterator obj = new NestedIterator(nest.getList());
        while (obj.hasNext()) {
            System.out.println(obj.next());
        }
    }
}

/**
 * 递归 + 迭代器
 */
class NestedIterator implements Iterator<Integer> {
    private Iterator<Integer> it = null;

    public NestedIterator(List<NestedInteger> nestedList) {
        List<Integer> list = new ArrayList<>();
        for (NestedInteger obj : nestedList) {
            // 通过递归“拍平”嵌套列表，元素顺序存储到 list 中
            dfs(obj, list);
        }
        // 生成 list 对象的迭代器对象
        it = list.iterator();
    }

    /**
     * 递归完成
     */
    public void dfs(NestedInteger obj, List<Integer> list) {
        if (obj.isInteger()) {
            list.add(obj.getInteger());
            return;
        }
        for (NestedInteger n : obj.getList()) {
            dfs(n, list);
        }
    }

    @Override
    public Integer next() {
        return it.next();
    }

    @Override
    public boolean hasNext() {
        return it.hasNext();
    }
}
